import java.util.ArrayList;
import java.util.List;

/**
 * 1286. 字母组合迭代器
 * https://leetcode-cn.com/problems/iterator-for-combination/
 */
public class Solutions_1286 {
    public static void main(String[] args) {
        CombinationIterator iterator = new CombinationIterator("abc", 2);

        String res1 = iterator.next();  // output: "ab"
        boolean res2 = iterator.hasNext();  // output: true
        String res3 = iterator.next(); // output: "ac"
        boolean res4 = iterator.hasNext(); // output: true
        String res5 = iterator.next(); // output: "bc"
        boolean res6 = iterator.hasNext(); // output: false
        System.out.println("");
    }
}

/**
 * 解法一：回溯算法优化（13ms）
 */
class CombinationIterator {
    List<String> list;
    int index;

    public CombinationIterator(String characters, int combinationLength) {
        list = new ArrayList<>();
        index = 0;
        char[] arr = characters.toCharArray();
        // 使用字符数组来代替 StringBuilder
        backtrack(arr, 0, new char[combinationLength], 0);
    }

    public String next() {
        return list.get(index ++);
    }

    public boolean hasNext() {
        return index < list.size();
    }

    public void backtrack(char[] arr, int start,
                          char[] subStr, int idx) {
        if (idx == subStr.length) {
            // 递归结束条件
            list.add(String.valueOf(subStr));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            subStr[idx] = arr[i];
            backtrack(arr, i + 1, subStr, idx + 1);
            // 使用数组的方式，省却了回溯还原的操作
        }
    }
}

/**
 * 解法一：回溯算法（18ms）
 */
class CombinationIterator2 {
    List<String> list;
    int idx;

    public CombinationIterator2(String characters, int combinationLength) {
        list = new ArrayList<>();
        idx = 0;
        char[] arr = characters.toCharArray();
        backtrack(arr, 0, combinationLength, new StringBuilder());
    }

    public String next() {
        return list.get(idx ++);
    }

    public boolean hasNext() {
        return idx < list.size();
    }

    public void backtrack(char[] arr, int start,
                                 int len, StringBuilder sb) {
        if (sb.length() == len) {
            list.add(sb.toString());
            return;
        }
        for (int i = start; i < arr.length; i++) {
            sb.append(arr[i]);
            backtrack(arr, i + 1, len, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
